Three-dimensional (3D) meshes have been widely used in various applications to represent 3D objects, including game, engineering design, architectural walkthrough, virtual reality, e-commerce, and scientific visualization. Their raw representation usually requires a huge amount of data, especially with the rapid growth of 3D scanners in recent years. However, most applications demand compact representation of 3D meshes for storage and transmission.
Typically, 3D meshes are represented by three types of data:
Topology data, which describe the adjacency relationship between vertices; it is also called connectivity data somewhere else. Geometry data, which specify vertex locations and property data, which specify attributes such as the normal vector, material reflectance, and texture coordinates.
Topology data and geometry data may be compressed commonly or separately. The coding order of geometry data is determined by the underlying topology coding. Geometry data is usually compressed by three main steps, quantization, prediction, and entropy coding. 3D mesh property data are usually compressed by the similar method of geometry compression.
Among the methods to encode topology data of 3D triangle meshes, Edgebreaker is a quite efficient and popularly used one proposed by J. Rossignac in: “Edgebreaker: Connectivity compression for triangle meshes,” IEEE Transactions on Visualization and Computer Graphics, Vol. 5, No. 1, pp. 47-61, January-March 1999.
For large meshes, Edgebreaker and entropy coding can yield less than 1.5 bits per triangle. Edgebreaker's compression and decompression processes perform identical traversals of the mesh from one triangle to an adjacent one. At each stage, compression produces bits to describe the topological relation between the current triangle and the boundary of the already encoded part of the mesh. Decompression decodes these bits to reconstruct the entire topology graph. By using Edgebreaker algorithm, all the topology data of 3D triangle mesh are a series of five possible mode symbols: “C”, “R”, “L”, “E”, and “S”. For example, the final output of Edgebreaker algorithm looks like: “CCRRRSLCRSERRELCRRRCRRRE . . . ”
Three of the five possible mode symbols of 3D mesh by Edgebreaker—“L” “E” “S”—do not occur as frequently as the other two symbols—“C” “R”—do. For example:
CRCRCRCRCLRECCRCRCRRCRLCCRRCRCRRCCRCRCCRSRCRCRCRRCRCR . . .
For example, the occurrences of the 5 modes in a couple of 3D mesh models:
TABLE 1Statistical result of the occurrences of the five modes ‘CRLES’ in different 3D models(b) VIP(c) Viewing(d)(e) Water(f)Modes(a) HallRoomroomProjectorMachineLaptop(g) PDAC31489124811945292103921103279912749(46.9%)(47.4%)(48.4%)(49.5%)(49.1%)(46.6%)(49.9%)R28724115672884421967220378271112082(42.7%)(43.9%)(45.3%)(46.3%)(47.3%)(45.2%)(47.3%)L249184794174114724674435 (3.7%) (3.2%) (2.1%) (2.7%) (0.6%) (1.2%) (1.7%)E317796214662343731259148 (4.7%) (3.7%) (2.4%) (0.8%) (1.7%) (4.3%) (0.6%)S135247233632285552160137 (2.0%) (1.8%) (1.9%) (0.7%) (1.3%) (2.7%) (0.5%)Total672332633061954394248643010600325551 (100%) (100%) (100%) (100%) (100%) (100%) (100%)